00-setup｜STL 最小必备

对应课程：lessons/00-setup/01-stl-minimum-for-icpc.md

你要会的“最少集合”

• vector：动态数组、排序、去重、前缀和容器 #
• string：遍历、拼接、子串（注意复杂度）#
• pair/tuple：打包数据 #
• sort：排序 + 自定义比较 #
• lower_bound/upper_bound：二分边界 #
• map/unordered_map：计数、映射、记录位置 #
• set/multiset：有序集合、前驱后继 #
• priority_queue：堆，维护最值 #

vector<T>

1. 动态数组

   • 动态：运行时根据需要自动扩容(push_back)
   • 数组：意味着在内存中连续存储。
     • 优点：支持**O(1)**时间的随机访问(v[i])
     • 缺点：在中间位置插入元素是O(n)的，因为需要移动后续元素

2. 声明与初始化

#include <vector>
#include <iostream>
using namespace std;

// 常用初始化方式
vector<int> v1; // 空vector
vector<int> v2(10); // 大小为10，每个元素为0
vector<int> v3(5, 99); // 大小为5，每个元素为99
vector<int> v4 = {1, 2, 3, 4, 5}; // C++11 列表初始化
vector<int> v5(v4.begin(), v4.end()); // 用迭代器范围初始化
vector<int> v6(v4); // 拷贝构造

// 竞赛中，为了避免初始化超时，常用reserve预分配空间
vector<int> v7;
v7.reserve(1000000); // 预分配约1M空间，避免多次扩容，但不改变size

3. 基础操作

vector<int> v;

//1.增
v.push_back(10); //在末尾添加，最常用. O(1)均摊
v.emplace_back(10); //C++11,效率稍高，直接构造
v.insert(v.begin()+2,99); //在指定位置插入. O(n)

//2.删
v.pop_back(); //删除末尾元素. O(1)
v.erase(v.begin()+1); //删除指定位置元素. O(n)
v.erase(v.begin()+1,v.begin()+4); //删除区间(first,last)
v.clear(); //清空

//3.查与改
int x=v[0]; //随机访问，不检查越界，最快
int y=v.at(0); //会检查越界，抛出异常，稍慢
v[1]=20; //直接修改
int first=v.front();//第一个元素
int last=v.back();//最后一个元素

//4.信息获取
int size=v.size(); //当前元素个数
bool isEmpty=v.empty(); //是否为空
int capacity=v.capacity(); //当前总容量（>=size）

补充 越界访问的判定

//CF22A
try {
        // 尝试访问第二个元素
        int second_smallest = a.at(1);
        cout << second_smallest;
    } catch (const std::out_of_range& e) {
        // 如果访问越界，说明没有第二个元素
        cout << "NO";
    }

4. 排序

#include <algorithm>
#include <vector>

vector<int> v={5,1,3,4,2};

//1.默认升序
sort(v.begin(),v.end()); //1,2,3,4,5

//2.降序排序
//2.1使用greater<int>()
sort(v.begin(),v.end(),greater<int>());

//2.2使用Lambda表达式（更灵活，C++11）
sort(v.begin(),v.end,[](int a,int b) {
    return a>b; //降序：a>b时，a排在前面
});

//3.自定义结构体排序
struct Node{
    int x,y;
};
vector<Node> nodes={{1,2},{3,1},{2,3}};
sort(nodes.begin(),nodes.end(),[](const Node& a,const Node& b){
    //先按x升序，x相同按y降序
    if (a.x!=b.x) return a.x<b.x;
    return a.y>b.y;
});

5. 去重(排序后使用)

非常经典的组合操作

vector<int> v={5,2,2,3,3,3,1};

//第一步：排序（去重前必须排序）
sort(v.begin(),v.end()); //1,2,2,3,3,3,5

//第二步:使用unique和erase
//unique将不重复的元素移到前面，返回新的“逻辑结束”迭代器
auto it = unique(v.begin(),v.end);
v.erase(it,v.end()); //删除后面重复的部分

//1,2,3,5

更简洁的写法

sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());

6. 前缀和容器

解决区间和查询问题的利器

vector<int> arr={1,2,3,4,5};
int n=arr.size();

//1.构造前缀和数组（技巧：大小设为n+1，方便处理边界）
vector<long long> prefix(n+1,0);
for (int i=0;i<n;i++){
    prefix[i+1]=prefix[i]+arr[i];
}
//prefix={0,1,3,6,10,15}

//2.查询区间[l,r]的和（下标从0开始）
int l=1,r=3;
long long sum=prefix[r+1]-prefix[l];//即prefix[4]-prefix[1]=10-1=9
//对应原数组arr[1]+arr[2]+arr[3]=2+3+4=9

//二维前缀和（也常用vector<vector<int>>存储）

7. 作为动态数组的高级用法

//1. 二维vector （动态二维数组）
vector<vector<int>> matrix(m,vector<int>(n,0)); //m行n列，初始为0
//访问：matrix[i][j]

//使用迭代器遍历（适用于需要修改元素时）
for (auto it=v.begin();it!=v.end();++it){
    *it+=10;
}

//3.范围for循环遍历（C++11,只读或需要拷贝时）
for (const auto& val:v){
    cout<<val<<" ";
}

8. 其他习得

• push_backvsemplace_back
  • 对于基本类型，两者无差别
  • 对于复杂对象（如结构体），emplace_back直接构造，避免拷贝，效率更高。建议习惯使用emplace_back。
• 警惕size的返回值类型：v.size()返回size_t（无符号整数）。在循环中与有符号数比较时，可能会出问题。

    // 危险！当 v 为空时，v.size()-1 会下溢变成一个很大的数
    for (int i = 0; i < v.size() - 1; i++) { ... }

    // 安全写法
    for (size_t i = 0; i + 1 < v.size(); i++) { ... }
    // 或显式转换
    for (int i = 0; i < (int)v.size() - 1; i++) { ... }

• 性能优化：
  • 如果提前知道大概元素数量，使用reverse(n)预分配空间，避免多次扩容拷贝。
  • 避免在循环中使用v.size()作为边界条件，提前保存：

int n=v.size();
for (int i=0;i<n;i++) {...}

• 清空vector的正确方式

vector<int>().swap(v); //彻底清空并释放内存
v.clear();//只清空元素，不释放内存（capacity不变）
v.shrink_to_fit();//C++11,请求释放未使用的内存

string字符串

之前已经自行学习整理，详见C++字符串

pair/tuple打包数据

pair

1. 基本概念 把两个数据打包成一个。

例如，

• 坐标（x,y）
• 区间[l,r]
• 键值对(key,value)
• 分数（分子，分母）

2. 声明与初始化

#include <iostream>
#include <utility> //pair的头文件
using namespace std;

//四种常用初始化方式
pair<int,int> p1; //默认构造（0，0）
pair<int, string> p2(1,"hello"); //直接构造
pair<int, double> p3={3,3.14}; //列表初始化（C++11）
auto p4=make_pair(4,"world"); //用make_pair，自动推导类型

小技巧：用make_pair比较省事，编译器自动推导类型

3. 访问元素 pair只有两个成员：.first和.second。

pair<int,int> point={10,20};
cout<<point.first<<" "<<point.second<<endl;

//修改也很简单
point.first=100;
point.second=200;

4. 使用场景 场景1:二维坐标

// 不用pair的写法（啰嗦）
int x1, y1, x2, y2;
// ...一堆计算...

// 用pair的写法（清晰）
pair<int, int> p1, p2;
p1 = {1, 2};
p2 = {3, 4};

场景二：存边（图论题超常见）

学习到这里还不知道什么是存边，什么是图论

// 存一条从u到v，权重为w的边
vector<pair<int, int>> edges;  // (v, w)
edges.push_back({3, 10});  // 从当前点到3，权重10

// 或者存完整边信息
vector<pair<pair<int, int>, int>> full_edges;  // ((u, v), w)

场景三：需要排序的复合数据

重点：pair自带比较规则，先比较.first，相等再比较.second。

vector<pair<int, int>> points = {{2, 3}, {1, 5}, {2, 1}, {1, 3}};

sort(points.begin(), points.end());
// 排序后：{1,3}, {1,5}, {2,1}, {2,3}
// 先按x排，x相同按y排

适用于很多贪心、排序题

5. pair实战：Dijkstra优先队列

pair在竞赛中的经典用法：

// 存储(距离, 节点编号)，用于Dijkstra算法的优先队列
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, start});  // 起点距离为0

while (!pq.empty()) {
    auto [dist, u] = pq.top();  // C++17结构化绑定，超好用！
    pq.pop();
    // ... 后续处理
}

这里用pair的妙处：优先队列默认比较第一个元素，所以距离最小的会先出队。

tuple:pair的升级版（三个及以上）

1. 什么时候用tuple?

打包三个或以上数据

比如：

• 一条完整的边（起点，终点，权重）
• 一个事件（时间，类型，参数）
• 三维坐标（x,y,z）

2. 基本操作

#include <tuple>

// 创建tuple（跟pair非常类似）
tuple<int, int, int> t1;  // 默认都是0
tuple<int, string, double> t2(1, "Alice", 95.5);
auto t3 = make_tuple(2, "Bob", 88.0);  // 自动推导

// 访问元素（注意：用get<>，下标是编译期常数）
cout << get<0>(t2) << endl;  // 输出1
cout << get<1>(t2) << endl;  // 输出"Alice"
cout << get<2>(t2) << endl;  // 输出95.5

// 修改元素
get<1>(t2) = "Charlie";

3. 竞赛中更优雅的写法：C++结构化绑定

// 创建tuple
auto student = make_tuple(1001, "张三", 85.5);

// 传统写法（啰嗦）
int id = get<0>(student);
string name = get<1>(student);
double score = get<2>(student);

// C++17结构化绑定（简洁明了）
auto [id, name, score] = student;
cout << id << " " << name << " " << score << endl;

4. tuple排序

和pair类似，tuple也按字典序比较：先比较第一个，相等再比较第二个，以此类推。

vector<tuple<int, int, int>> edges = {
    {1, 3, 10},
    {1, 2, 5},
    {2, 3, 8},
    {1, 2, 3}
};

sort(edges.begin(), edges.end());
// 排序后：
// {1,2,3}, {1,2,5}, {1,3,10}, {2,3,8}

pairvstuplevs结构体：怎么选？

1. 只有两个数据 → 用pair

2. 三个及以上数据 → 用tuple（特别是临时用一下的情况）

3. 需要添加成员函数/方法 → 用struct（比如要自定义比较函数）

e.g.

// 情况1：存点坐标 → pair
pair<int, int> point = {x, y};

// 情况2：存边信息 → tuple（如果只是存一下）
auto edge = make_tuple(u, v, w);

// 情况3：复杂的节点信息 → struct
struct Node {
    int id;
    string name;
    double score;
    
    // 可以自定义比较函数
    bool operator<(const Node& other) const {
        return score > other.score;  // 按分数降序
    }
};

实战技巧

技巧1:配合vector使用

// 存一堆点
vector<pair<int, int>> points;
points.push_back({x, y});

// 存图（邻接表）
vector<vector<pair<int, int>>> graph(n);  // graph[u] = [(v1, w1), (v2, w2), ...]
graph[u].push_back({v, w});

// 存多个属性
vector<tuple<int, string, int>> students;  // (学号, 姓名, 年龄)

技巧2:自定义比较函数

// pair自定义排序：先按second升序，再按first降序
vector<pair<int, int>> data = {{1, 3}, {2, 1}, {3, 1}};
sort(data.begin(), data.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
    if (a.second != b.second) return a.second < b.second;
    return a.first > b.first;
});
// 结果：{2,1}, {3,1}, {1,3}

技巧3:使用tie(C++11)解包

tuple<int, int, int> getThreeValues() {
    return {1, 2, 3};
}

int x, y, z;
tie(x, y, z) = getThreeValues();  // x=1, y=2, z=3

// tie还可以忽略某些值
tie(x, ignore, z) = getThreeValues();  // 只取第一和第三个

常见坑

错误1:类型不匹配

pair<int, string> p = {3.14, "pi"};  // 错误！3.14是double，不是int
auto p = make_pair(3.14, "pi");      // 正确，自动推导为pair<double, string>

错误2:忘记包含头文件（但是用万能头一般不会出问题）

// 需要这些头文件（或者直接用<bits/stdc++.h>）
#include <utility>   // pair
#include <tuple>     // tuple

**错误3:get<>的下标是编译器常数

tuple<int, int, int> t = {1, 2, 3};
int idx = 1;
cout << get<idx>(t) << endl;  // 错误！idx必须是编译期常数
cout << get<1>(t) << endl;    // 正确

sort排序+自定义比较

使用方式

• 数组排序

int arr[]={5,2,8,1,3};
sort(arr,arr+5); //升序

• vector排序

vector<int> v={5,2,8,1,3};
sort(v.begin(),v.end());//升序

• 降序排序（两种方式）

sort(v.begin(),v.end(),greater<int>); //方法1
sort(v.rbegin(),v.rend()); //方法2:反向迭代器

• pair排序

//先按first，再按second
vector<pair<int,int>> points={{1,3},{2,1},{1,2}};
sort(points.begin(),points.end());

• 结构体排序

struct Node {
    int x,y;
};
vector<Node> nodes={{1,3},{2,1},{1,2}};
sort(nodes.begin(),nodes.end(),[](Node a, Node b) {
    if (a.x != b.x) return a.x<b.x;
    return a.y<b.y;
});

自定义比较：核心技能

1. 三种自定义比较方式

• 方式1:使用Lambda表达式(常用)

vector<int> v = {5, 2, 8, 1, 3};

// 升序（默认）
sort(v.begin(), v.end(), [](int a, int b) {
    return a < b;
});

// 降序
sort(v.begin(), v.end(), [](int a, int b) {
    return a > b;
});

// 按绝对值排序
sort(v.begin(), v.end(), [](int a, int b) {
    return abs(a) < abs(b);
});

• 方式2:自定义比较函数

bool cmp(int a, int b) {
    // 奇数在前，偶数在后，相同大小按升序
    if (a % 2 != b % 2) return a % 2 > b % 2;
    return a < b;
}

vector<int> v = {1, 4, 2, 7, 5, 6};
sort(v.begin(), v.end(), cmp);  // 结果：1,5,7,2,4,6

• 方式3:重载运算符（适合结构体）

struct Point {
    int x, y;
    
    // 重载小于运算符
    bool operator<(const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
};

vector<Point> points = {{1,3}, {2,1}, {1,2}};
sort(points.begin(), points.end());  // 自动使用重载的<

2. 多关键字排序模版

// 三个关键字的排序：先按a降序，再按b升序，最后按c降序
struct Data {
    int a, b, c;
};

vector<Data> vec;
sort(vec.begin(), vec.end(), [](const Data& x, const Data& y) {
    if (x.a != y.a) return x.a > y.a;      // a降序
    if (x.b != y.b) return x.b < y.b;      // b升序  
    return x.c > y.c;                      // c降序
});

竞赛实战技巧

1. 字符串特殊排序

// 按长度排序，长度相同按字典序
vector<string> words = {"apple", "cat", "banana", "dog"};
sort(words.begin(), words.end(), [](const string& a, const string& b) {
    if (a.size() != b.size()) return a.size() < b.size();
    return a < b;
});
// 结果：cat, dog, apple, banana

2. 下标排序（间接排序）

// 场景：需要知道排序后每个元素原来的位置
vector<int> v = {30, 10, 20};
vector<int> idx = {0, 1, 2};  // 原始下标

// 按v的值对下标排序
sort(idx.begin(), idx.end(), [&](int i, int j) {
    return v[i] < v[j];  // 通过下标访问原数组
});

// idx变为：1,2,0（表示原数组第1个元素最小）

3. 稳定排序（stable_sort）

// stable_sort保持相等元素的原始相对顺序
vector<pair<int, string>> students = {
    {85, "Alice"},
    {90, "Bob"},
    {85, "Charlie"}
};

// 按分数升序，相同分数保持输入顺序
stable_sort(students.begin(), students.end(), 
            [](auto& a, auto& b) { return a.first < b.first; });
// Alice和Charlie的相对顺序不变

高频考点与易错点

1. 比较函数必须严格弱序

// 错误示例：违反严格弱序
sort(v.begin(), v.end(), [](int a, int b) {
    return a <= b;  // 错误！不能有等于
});

// 正确写法
sort(v.begin(), v.end(), [](int a, int b) {
    return a < b;  // 必须是严格小于
});

2. 性能优化：减少拷贝(其实没怎么懂)

// 对于大对象，使用引用避免拷贝
struct BigObject {
    int data[1000];
    // ... 其他成员
};

vector<BigObject> vec;
sort(vec.begin(), vec.end(), [](const BigObject& a, const BigObject& b) {
    return a.data[0] < b.data[0];  // 使用const引用
});

3. 复杂结构体排序优化

// 方法1：一次性计算比较键（避免重复计算）
sort(vec.begin(), vec.end(), [](const Node& a, const Node& b) {
    int keyA = a.x * 1000 + a.y;  // 假设x,y范围已知
    int keyB = b.x * 1000 + b.y;
    return keyA < keyB;
});

// 方法2：预计算+Lambda捕获（C++14）
auto getKey = [](const Node& n) { return n.x * 1000 + n.y; };
sort(vec.begin(), vec.end(), 
     [&](const Node& a, const Node& b) { return getKey(a) < getKey(b); });

lower_bound/upper_bound：二分边界

算法竞赛中二分查找的两个核心武器，彻底搞懂边界问题

基础概念辨析(两者区别)

• lower_bound(开始,结束,值)：找到第一个>=目标值的位置
• upper_bound(开始,结束,值)：找到第一个>目标值的位置

基础用法

1. 基本语法

    vector<int> v = {1, 2, 2, 3, 3, 3, 4, 5};
    
    // lower_bound: 找到第一个 >= 3 的位置
    auto lb = lower_bound(v.begin(), v.end(), 3);
    cout << "第一个3在位置: " << (lb - v.begin()) << endl; // 输出3
    
    // upper_bound: 找到第一个 > 3 的位置  
    auto ub = upper_bound(v.begin(), v.end(), 3);
    cout << "第一个大于3在位置: " << (ub - v.begin()) << endl; // 输出6
    
    // 元素3的个数 = ub - lb
    cout << "元素3的个数: " << (ub - lb) << endl; // 输出3

2. 重要特性：找不到的情况

vector<int> v = {1, 2, 4, 5};

auto lb = lower_bound(v.begin(), v.end(), 3);
if (lb == v.end()) {
    cout << "没有找到 >=3 的元素" << endl;
} else {
    cout << "第一个 >=3 的元素是: " << *lb << endl; // 输出4
}

auto ub = upper_bound(v.begin(), v.end(), 5);
if (ub == v.end()) {
    cout << "没有找到 >5 的元素" << endl; // 会输出这个
}

竞赛实战：常见用法

1. 查找元素是否存在（替代find的更快二分法）

// 在有序数组中查找元素是否存在（比find快，O(logn)）
bool binaryExists(const vector<int>& v, int target) {
    auto it = lower_bound(v.begin(), v.end(), target);
    return it != v.end() && *it == target;
}

// 使用示例
vector<int> v = {1, 3, 5, 7, 9};
cout << binaryExists(v, 5) << endl; // 输出1（true）
cout << binaryExists(v, 6) << endl; // 输出0（false）

2. 统计区间内元素个数

// 统计有序数组中 [L, R] 范围内的元素个数
int countInRange(const vector<int>& v, int L, int R) {
    auto left = lower_bound(v.begin(), v.end(), L);
    auto right = upper_bound(v.begin(), v.end(), R);
    return right - left;
}

// 使用示例
vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
cout << countInRange(v, 3, 7) << endl; // 输出5（3,4,5,6,7）

3. 插入位置计算（保持有序性）

// 在有序数组中插入元素，保持有序
void insertOrdered(vector<int>& v, int value) {
    auto pos = lower_bound(v.begin(), v.end(), value);
    v.insert(pos, value);
}

// 使用示例
vector<int> v = {1, 3, 5, 7};
insertOrdered(v, 4); // v变为 [1,3,4,5,7]
insertOrdered(v, 0); // v变为 [0,1,3,4,5,7]

自定义比较：处理复杂的数据结构

1. 对pair数组使用二分查找

// 按照pair的第一个元素查找
vector<pair<int, int>> points = {
    {1, 10}, {2, 20}, {3, 30}, {4, 40}, {5, 50}
};

// 找到第一个 first >= 3 的pair
auto it = lower_bound(points.begin(), points.end(), 
                      make_pair(3, INT_MIN));
// 注意：要提供完整的pair，这里用INT_MIN表示第二个元素不限制

if (it != points.end()) {
    cout << "找到: (" << it->first << "," << it->second << ")" << endl;
}

2. 自定义比较函数（处理结构体）

struct Student {
    int id;
    string name;
    int score;
};

vector<Student> students={
    {101, "Alice", 85},
    {102, "Bob", 92},
    {103, "Charlie", 78},
    {104, "David", 92}
};

//按分数排序
sort(students.begin(),students.end(),[](const Student& a,const Student& b) {
    return a.score<b.score;
});

//查找第一个分数>=90的学生
Student target{0,"",90};//只用score字段比较
auto it=lower_bound(students.begin(),students.end(),target,[](const Student& a,const Student& b){
    return a.score<b.score;
});

3. 降序数组的处理

// 降序数组：需要自定义比较函数
vector<int> v = {9, 7, 5, 3, 1};

// 在降序数组中找第一个 <= target 的位置（相当于升序的 >=）
int target = 4;
auto it = lower_bound(v.begin(), v.end(), target, greater<int>());
// 这里比较函数是greater，所以找的是第一个 <= target 的位置

if (it != v.end()) {
    cout << *it << endl; // 输出3（第一个 <=4 的元素）
}

竞赛高级技巧

1. 使用distance避免类型混淆

vector<int> v={1,2,3,4,5};

//获取位置索引的两种方法
int idx1 = lower_bound(v.begin(),v.end(),3)-v.begin(); //方法1
int idx2 = distance(v.begin(),lower_bound(v.begin(),v.end(),3)); //方法2

//推荐方法2，避免类型转换问题，且通用型更好

2. 配合set/map使用

set<int> s = {1, 3, 5, 7, 9};

// set也有lower_bound方法，但用法不同
auto it = s.lower_bound(4);  // 直接调用成员函数
if (it != s.end()) {
    cout << *it << endl;  // 输出5
}

3. 实现自己的二分查找

有时候需要自定义二分查找，所以理解原理很重要

int binarySearch(const vector<int>& v, int target) {
    int left = 0, right = v.size() - 1;
    int ans = v.size();  // 初始化为数组长度（表示找不到）
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (v[mid] >= target) {  // 相当于lower_bound
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;  // 返回第一个 >= target 的位置
}

常见错误

1. 忘记排序直接lower_bound
2. 错误使用end()迭代器

vector<int> v = {1, 2, 3};
auto it = lower_bound(v.begin(), v.end(), 5);

// 必须检查是否找到
if (it != v.end()) {
    // 安全使用
    cout << *it << endl;
} else {
    cout << "没找到" << endl;  // 会执行这里
}

3. 混淆lower_bound和upper_bound

// 统计元素x的个数
vector<int> v = {1, 2, 2, 2, 3};
int x = 2;

// 错误：直接用upper_bound
int wrong = upper_bound(v.begin(), v.end(), x) - v.begin();  // 返回4

// 正确：用upper_bound - lower_bound
int correct = upper_bound(v.begin(), v.end(), x) 
            - lower_bound(v.begin(), v.end(), x);  // 返回3

4. 类型不匹配

vector<long long> v = {1, 2, 3, 4, 5};
long long target = 3;

// 错误：target是long long，但用了int版本
auto it = lower_bound(v.begin(), v.end(), (int)target);  // 可能没问题，但不安全

// 正确：保持类型一致
auto it = lower_bound(v.begin(), v.end(), target);  // 推荐

map/unordered_map：计数、映射、记录位置

核心概念：什么是映射？

映射是一种对应关系，比如：

• 单词->出现次数
• 学生ID->姓名
• 坐标->该坐标的点数

C++提供了两种主要的映射容器：

1. map：基于红黑树实现，按键有序存储，操作复杂度$O(logn)$
2. unordered_map：基于哈希表实现，按键无序存储，操作平均$O(1)$，最坏$O(n)$

map：有序映射

1. 基本操作

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 声明
    map<string, int> mp;
    
    // 插入数据的三种方式
    mp["apple"] = 5;           // 方式1：直接赋值
    mp.insert({"banana", 3});  // 方式2：insert插入pair
    mp.insert(make_pair("orange", 8)); // 方式3：make_pair
    
    // 访问元素（如果不存在会自动创建，值为默认值0）
    cout << mp["apple"] << endl;  // 输出5
    
    // 判断元素是否存在（重要！）
    if (mp.count("grape") > 0) {
        cout << "grape exists" << endl;
    }
    
    // 或者用find（更推荐）
    auto it = mp.find("banana");
    if (it != mp.end()) {
        cout << it->first << ": " << it->second << endl;
    }
    
    // 遍历（按键升序）
    for (auto& [key, value] : mp) {  // C++17结构化绑定
        cout << key << ": " << value << endl;
    }
    
    // 删除元素
    mp.erase("apple");
    
    return 0;
}

2. map的特性

• 按键自动排序：遍历时按键的升序输出（字符串按字典序）
• 键唯一：每个键只能出现一次
• 查找效率：$O(logn)$，n是元素个数

unordered_map：速度优先的选择

1. 基本操作（与map基本相同）

#include <unordered_map>

int main() {
    unordered_map<string, int> ump;
    
    // 插入和访问与map一样
    ump["apple"] = 5;
    cout << ump["apple"] << endl;
    
    // 判断存在性也一样
    if (ump.find("apple") != ump.end()) {
        // 存在
    }
    
    // 遍历（但顺序是不确定的！）
    for (auto& kv : ump) {
        cout << kv.first << ": " << kv.second << endl;
    }
    
    return 0;
}

2. unordered_map的特性

• 无序：遍历顺序不确定，可能每次运行都不同
• 平均$O(1)$操作：插入、查找、删除的平均时间复杂度都是O(1)
• 最坏$O(n)$：哈希冲突严重时性能下降
• 自定义键类型需要哈希函数：先从略

如何选择两者

选择依据：

特性	map	unordered_map
内部实现	红黑树	哈希表
元素顺序	按键有序	无序
时间复杂度	$O(logn)$	平均$O(1)$，最坏$O(n)$
空间复杂度	较低	较高（哈希表有负载因子）
键的要求	必须可比较（实现<运算符）	必须可哈希（有哈希函数）

使用建议总结

1. 需要顺序遍历 -> 用map
2. 只需要快速查找，不关心顺序 -> 用unordered_map
3. 不确定时，默认用unordered_map，因为通常更快

实际使用场景

场景1:计数（统计频率）

// 统计数组中每个元素出现的次数
vector<int> arr = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4};

// 方法1：使用unordered_map（更快）
unordered_map<int, int> cnt1;
for (int x : arr) {
    cnt1[x]++;  // 如果x不存在，会自动创建并初始化为0
}

// 方法2：使用map（如果需要按key顺序输出）
map<int, int> cnt2;
for (int x : arr) {
    cnt2[x]++;
}

// 输出统计结果
for (auto& [num, count] : cnt2) {
    cout << num << "出现" << count << "次" << endl;
}

场景2:映射（建立对应关系）

// 建立学生ID到姓名的映射
map<int, string> idToName;
idToName[1001] = "Alice";
idToName[1002] = "Bob";
idToName[1003] = "Charlie";

// 查找ID为1002的学生
auto it = idToName.find(1002);
if (it != idToName.end()) {
    cout << "找到学生: " << it->second << endl;
}

// 反向映射：姓名到ID
map<string, int> nameToId;
for (auto& [id, name] : idToName) {
    nameToId[name] = id;
}

场景3:记录位置（第一次出现的位置）

// 记录每个元素第一次出现的下标
vector<int> arr = {5, 2, 5, 1, 2, 5, 3};
unordered_map<int, int> firstPos;

for (int i = 0; i < arr.size(); i++) {
    int num = arr[i];
    if (firstPos.find(num) == firstPos.end()) {
        firstPos[num] = i;  // 只记录第一次出现
    }
}

// 查询数字5第一次出现的位置
if (firstPos.count(5)) {
    cout << "5第一次出现在下标" << firstPos[5] << endl;
}

进阶技巧：需要自定义比较函数

1. map:需要自定义比较函数

struct Point {
    int x, y;
    
    // map需要比较函数，所以重载<运算符
    bool operator<(const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
};

int main() {
    map<Point, int> pointValue;
    pointValue[{1, 2}] = 10;
    pointValue[{3, 4}] = 20;
    
    return 0;
}

2. unordered_map:需要自定义哈希函数

struct Point {
    int x, y;
    
    // 需要重载==运算符
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// 自定义哈希函数
struct PointHash {
    size_t operator()(const Point& p) const {
        // 简单的哈希组合：将两个整数合并成一个
        return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
    }
};

int main() {
    unordered_map<Point, int, PointHash> pointValue;
    pointValue[{1, 2}] = 10;
    pointValue[{3, 4}] = 20;
    
    return 0;
}

常见错误

1. 使用不存在的键访问（自动创建）

map<string, int> mp;
cout << mp["unknown"] << endl;  // 输出0，但会创建键"unknown"

// 正确做法：先检查是否存在
if (mp.find("unknown") != mp.end()) {
    cout << mp["unknown"] << endl;
}

2. 遍历时删除元素

map<int, int> mp = {{1, 10}, {2, 20}, {3, 30}};

// 错误：遍历时直接删除
for (auto it = mp.begin(); it != mp.end(); ++it) {
    if (it->first == 2) {
        mp.erase(it);  // 错误！it失效
    }
}

// 正确：先保存迭代器
for (auto it = mp.begin(); it != mp.end(); ) {
    if (it->first == 2) {
        it = mp.erase(it);  // erase返回下一个有效迭代器
    } else {
        ++it;
    }
}

3. unordered_map的自定义键类型

// 错误：自定义结构体作为unordered_map的键，但没有提供哈希函数
struct MyKey {
    int a, b;
};

unordered_map<MyKey, int> mp;  // 编译错误！

// 需要提供哈希函数，如前文所示

性能优化技巧

1. 预分配空间（unordered_map）

// 如果知道大概元素数量，可以预分配bucket数量，减少rehash
unordered_map<int, int> mp;
mp.reserve(10000);  // 预分配大约10000个元素的空间

2. 使用emplace替代insert

map<int, string> mp;

// insert需要创建pair
mp.insert(make_pair(1, "one"));

// emplace直接构造，效率更高（C++11）
mp.emplace(2, "two");

3. 查找时用find而不是count

// 较慢：需要计数
if (mp.count(key) > 0) {
    // ...
}

// 较快：直接查找
auto it = mp.find(key);
if (it != mp.end()) {
    // ...
}

set/multiset：有序集合、前驱后继

set与multiset：算法竞赛中的有序集合利器

一、核心概念：有序集合是什么？

想象你有一个自动整理的工具箱：

• set：每个工具只有一件，按大小自动排列
• multiset：工具可以有多件相同的，也按大小排列

一句话说清楚：

• set：元素唯一的有序集合
• multiset：元素可重复的有序集合

两者内部都是红黑树实现，保证操作复杂度为O(log n)，且元素始终自动排序。

二、set：唯一的自动排序集合

1. 基础操作

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 1. 创建和初始化
    set<int> s1;                     // 空集合
    set<int> s2 = {3, 1, 4, 1, 5};   // 自动去重：{1, 3, 4, 5}
    
    // 2. 插入元素
    s1.insert(10);
    s1.insert(20);
    s1.insert(30);
    s1.insert(20);  // 重复插入，不会有效果
    
    // 3. 判断元素是否存在
    if (s1.count(20)) {  // 返回1表示存在
        cout << "20存在" << endl;
    }
    // 或使用find（更常用）
    if (s1.find(20) != s1.end()) {
        cout << "20存在" << endl;
    }
    
    // 4. 删除元素
    s1.erase(20);     // 删除值为20的元素
    s1.erase(s1.begin());  // 删除第一个元素
    
    // 5. 遍历（自动升序）
    for (int x : s2) {
        cout << x << " ";  // 输出：1 3 4 5
    }
    cout << endl;
    
    // 6. 获取大小和清空
    cout << "大小: " << s1.size() << endl;
    s1.clear();  // 清空集合
    
    return 0;
}

2. set的重要特性

• 元素自动去重：相同的值只会保留一个
• 自动排序：默认按升序排列
• 查找快速：O(log n)时间判断元素是否存在
• 迭代器稳定：插入删除不会使其他迭代器失效（除了被删除的）

三、multiset：可重复的有序集合

1. 基础操作（与set相似但有区别）

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 创建multiset（允许重复）
    multiset<int> ms = {1, 2, 2, 3, 3, 3};
    
    // 插入元素（允许重复）
    ms.insert(2);  // 现在有三个2
    
    // 统计某个值的个数
    cout << "2的个数: " << ms.count(2) << endl;  // 输出3
    
    // 删除元素（重要区别！）
    // 方式1：删除所有值为2的元素
    ms.erase(2);  // 删除所有2
    
    // 方式2：只删除一个2（需要先找到迭代器）
    ms.insert(2);  // 重新添加一个2
    auto it = ms.find(2);  // 找到任意一个2
    if (it != ms.end()) {
        ms.erase(it);  // 只删除这个迭代器指向的元素
    }
    
    // 遍历（自动排序）
    for (int x : ms) {
        cout << x << " ";  // 输出：1 3 3 3
    }
    
    return 0;
}

2. multiset与set的区别

操作	set	multiset
插入重复元素	忽略	允许
erase(value)	删除1个	删除所有值为value的元素
count(value)	0或1	可能有多个

四、竞赛核心：前驱后继查找

这是set/multiset在竞赛中最重要的功能！

1. 什么是前驱和后继？

有序集合：[1, 3, 5, 7, 9]
查找值：6

前驱：第一个 < 6 的元素 → 5
后继：第一个 > 6 的元素 → 7

2. 查找方法

set<int> s = {1, 3, 5, 7, 9};
int target = 6;

// 方法1：使用lower_bound和upper_bound
auto it_low = s.lower_bound(target);  // 第一个 >= 6 → 指向7
auto it_up = s.upper_bound(target);   // 第一个 > 6 → 指向7

// 方法2：手动找前驱和后继（更常用）
auto it = s.lower_bound(target);  // 指向第一个 >= target的元素

// 找前驱（小于target的最大元素）
if (it != s.begin()) {
    auto prev_it = prev(it);  // 前驱迭代器
    cout << "前驱: " << *prev_it << endl;  // 输出5
}

// 找后继（大于target的最小元素）
if (it != s.end()) {
    cout << "后继: " << *it << endl;  // 输出7
}

3. 实用模板函数

// 查找前驱（小于x的最大值，不存在返回-INF）
int findPredecessor(set<int>& s, int x) {
    auto it = s.lower_bound(x);
    if (it == s.begin()) {
        return INT_MIN;  // 没有前驱
    }
    return *prev(it);
}

// 查找后继（大于x的最小值，不存在返回INF）
int findSuccessor(set<int>& s, int x) {
    auto it = s.upper_bound(x);
    if (it == s.end()) {
        return INT_MAX;  // 没有后继
    }
    return *it;
}

// 查找最近的值（前驱和后继中更接近的）
int findNearest(set<int>& s, int x) {
    int pred = findPredecessor(s, x);
    int succ = findSuccessor(s, x);
    
    if (pred == INT_MIN) return succ;
    if (succ == INT_MAX) return pred;
    
    return (x - pred <= succ - x) ? pred : succ;
}

五、自定义比较函数

1. 降序集合

// 方法1：使用greater<int>
set<int, greater<int>> s1;  // 降序集合
s1.insert({1, 3, 2, 5, 4});
for (int x : s1) cout << x << " ";  // 输出：5 4 3 2 1

// 方法2：自定义比较函数
struct Compare {
    bool operator()(int a, int b) const {
        return a > b;  // 降序
    }
};
set<int, Compare> s2;

2. 结构体集合

struct Point {
    int x, y;
    
    // 需要重载<运算符，因为set需要比较
    bool operator<(const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
};

int main() {
    set<Point> points;
    points.insert({1, 2});
    points.insert({3, 4});
    points.insert({1, 3});  // 可以插入，因为(1,3) != (1,2)
    
    return 0;
}

六、竞赛实战应用

应用1：维护动态有序序列

// 实时查询数据流中的中位数
multiset<int> left, right;  // left存较小的一半，right存较大的一半

void addNum(int num) {
    // 先插入到left
    left.insert(num);
    
    // 平衡两个集合，保证left的大小 >= right的大小
    // 且left的最大值 <= right的最小值
    if (!left.empty() && !right.empty() && *left.rbegin() > *right.begin()) {
        right.insert(*left.rbegin());
        left.erase(prev(left.end()));
    }
    
    // 调整大小，保持平衡
    if (left.size() > right.size() + 1) {
        right.insert(*left.rbegin());
        left.erase(prev(left.end()));
    } else if (right.size() > left.size()) {
        left.insert(*right.begin());
        right.erase(right.begin());
    }
}

double findMedian() {
    if (left.size() > right.size()) {
        return *left.rbegin();
    }
    return (*left.rbegin() + *right.begin()) / 2.0;
}

应用2：区间查询问题

// 查询与x最接近的值（用于最近点对等问题）
int queryClosest(set<int>& s, int x) {
    if (s.empty()) return -1;
    
    auto it = s.lower_bound(x);
    int ans = -1;
    
    // 检查后继
    if (it != s.end()) {
        ans = *it;
    }
    
    // 检查前驱
    if (it != s.begin()) {
        auto prev_it = prev(it);
        if (ans == -1 || abs(*prev_it - x) < abs(ans - x)) {
            ans = *prev_it;
        }
    }
    
    return ans;
}

应用3：滑动窗口最大值（使用multiset）

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> result;
    multiset<int> window;
    
    for (int i = 0; i < nums.size(); i++) {
        window.insert(nums[i]);
        
        // 窗口满了
        if (window.size() > k) {
            window.erase(window.find(nums[i - k]));
        }
        
        // 记录当前窗口最大值
        if (window.size() == k) {
            result.push_back(*window.rbegin());  // multiset的最大值
        }
    }
    
    return result;
}

七、常见错误与坑点

1. 直接修改set中的元素（错误！）

set<int> s = {1, 2, 3};
auto it = s.find(2);
if (it != s.end()) {
    *it = 5;  // 错误！不能直接修改，会破坏红黑树结构
}

// 正确做法：先删除，再插入
int old_value = *it;
s.erase(it);
s.insert(5);

2. multiset删除所有相同元素

multiset<int> ms = {1, 2, 2, 2, 3};

// 想删除一个2，结果删除了所有2
ms.erase(2);  // 删除了所有2

// 正确做法：删除一个2
auto it = ms.find(2);
if (it != ms.end()) {
    ms.erase(it);  // 只删除一个
}

3. 边界检查

set<int> s = {10, 20, 30};

// 查找前驱时的边界检查
auto it = s.lower_bound(5);  // 指向10（第一个>=5的）
if (it != s.begin()) {
    // 安全访问前驱
    cout << "前驱: " << *prev(it) << endl;
} else {
    cout << "没有前驱" << endl;
}

八、性能优化技巧

1. 使用unordered_set当不需要顺序

// 只需要判断存在性，不需要顺序
unordered_set<int> us;  // O(1)查找，但不保证顺序
us.insert(5);
us.insert(1);
us.insert(3);

// 遍历顺序不确定
for (int x : us) {
    cout << x << " ";  // 可能是任何顺序
}

2. 合并两个集合

set<int> s1 = {1, 3, 5};
set<int> s2 = {2, 4, 6};

// 高效合并
s1.insert(s2.begin(), s2.end());  // O(n log n)

// 对于multiset也可以
multiset<int> ms1 = {1, 2, 2};
multiset<int> ms2 = {2, 3};
ms1.insert(ms2.begin(), ms2.end());

九、实战代码模板

#include <bits/stdc++.h>
using namespace std;

class SetUtils {
public:
    // 模板1：维护动态有序数组的基本操作
    template<typename T>
    class OrderedSet {
    private:
        set<T> s;
    public:
        void insert(T val) { s.insert(val); }
        bool contains(T val) { return s.find(val) != s.end(); }
        void remove(T val) { s.erase(val); }
        
        // 前驱（小于val的最大值）
        T predecessor(T val) {
            auto it = s.lower_bound(val);
            if (it == s.begin()) return T();  // 默认值
            return *prev(it);
        }
        
        // 后继（大于val的最小值）
        T successor(T val) {
            auto it = s.upper_bound(val);
            if (it == s.end()) return T();  // 默认值
            return *it;
        }
        
        // 获取最小值和最大值
        T getMin() { return s.empty() ? T() : *s.begin(); }
        T getMax() { return s.empty() ? T() : *s.rbegin(); }
    };
    
    // 模板2：使用multiset维护滑动窗口最值
    static vector<int> slidingWindowMax(vector<int>& nums, int k) {
        vector<int> res;
        multiset<int> ms;
        
        for (int i = 0; i < nums.size(); i++) {
            ms.insert(nums[i]);
            if (ms.size() > k) {
                ms.erase(ms.find(nums[i - k]));
            }
            if (ms.size() == k) {
                res.push_back(*ms.rbegin());
            }
        }
        return res;
    }
    
    // 模板3：使用set去重并排序
    template<typename T>
    static vector<T> uniqueSorted(const vector<T>& arr) {
        set<T> s(arr.begin(), arr.end());
        return vector<T>(s.begin(), s.end());
    }
};

int main() {
    // 示例使用
    SetUtils::OrderedSet<int> os;
    os.insert(10);
    os.insert(20);
    os.insert(30);
    
    cout << "前驱15: " << os.predecessor(15) << endl;  // 10
    cout << "后继25: " << os.successor(25) << endl;    // 30
    
    // 滑动窗口最大值示例
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    vector<int> result = SetUtils::slidingWindowMax(nums, k);
    
    return 0;
}

十、总结要点

1. 核心区别：

   • set：元素唯一，自动排序
   • multiset：元素可重复，自动排序

2. 主要用途：

   • 去重并排序
   • 维护动态有序序列
   • 快速查找前驱后继
   • 滑动窗口最值维护

3. 关键操作：

   • insert()：插入元素
   • find() / count()：查找元素
   • erase()：删除元素
   • lower_bound() / upper_bound()：边界查找

4. 注意事项：

   • multiset的erase(value)会删除所有相同值
   • 不能直接修改set中的元素
   • 查找前驱后继时要检查边界

十一、选择指南

• 需要去重且有序 → set
• 允许重复且需要有序 → multiset
• 只需要判断存在性，不在乎顺序 → unordered_set
• 需要快速找到最接近的值 → set（利用自动排序）

在算法竞赛中，set/multiset常用于需要动态维护有序序列的场景。掌握好前驱后继的查找，很多难题就能迎刃而解。

priority_queue：堆，维护最值

priority_queue：算法竞赛中的堆与最值维护利器

一、核心概念：什么是优先队列？

优先队列就是一个自动排序的队列，但和普通队列不同：

• 普通队列：先进先出（FIFO）
• 优先队列：优先级最高的先出（不是按插入顺序）

想象一下医院急诊室：

• 普通队列：先来的先看
• 优先队列：病情最重的先看，不管什么时候来的

底层实现：通常用二叉堆（一种完全二叉树）实现，能在O(1)时间获取最值，O(log n)时间插入和删除。

二、基本操作：快速上手

1. 两种优先队列的创建

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 1. 最大堆（默认）：堆顶是最大值
    priority_queue<int> maxHeap;
    
    // 2. 最小堆：堆顶是最小值
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    // 3. 带初始数据的创建
    vector<int> nums = {3, 1, 4, 1, 5};
    priority_queue<int> maxHeap2(nums.begin(), nums.end());
    
    return 0;
}

2. 基本操作（与栈操作类似）

priority_queue<int> pq;

// 1. 插入元素
pq.push(10);  // O(log n)
pq.push(5);
pq.push(20);
pq.push(15);

// 2. 获取堆顶元素（最大值）
cout << pq.top() << endl;  // 输出20

// 3. 删除堆顶元素
pq.pop();  // 删除20，O(log n)

// 4. 获取大小和判断空
cout << "大小: " << pq.size() << endl;  // 现在有3个
cout << "是否空: " << pq.empty() << endl;

// 5. 清空优先队列（没有clear函数）
// 方法1：循环pop
while (!pq.empty()) pq.pop();

// 方法2：重新构造
pq = priority_queue<int>();

3. 重要特性

• 只能访问堆顶：不能随机访问其他元素
• 自动排序：插入时自动维护堆结构
• 没有迭代器：不能遍历（除非边pop边遍历）
• 默认最大堆：C++的priority_queue默认是最大堆

三、自定义比较函数：竞赛核心技能

1. 自定义结构体：重载运算符

struct Node {
    int x, y;
    int value;
    
    // 方法1：重载<运算符（最大堆）
    bool operator<(const Node& other) const {
        // 注意：返回true表示优先级低，false表示优先级高
        return value < other.value;  // 值大的优先级高（最大堆）
    }
};

int main() {
    priority_queue<Node> pq;  // 最大堆，按value从大到小
    
    pq.push({1, 2, 10});
    pq.push({3, 4, 5});
    pq.push({5, 6, 15});
    
    cout << pq.top().value << endl;  // 输出15（最大值）
    
    return 0;
}

2. 自定义比较类（更灵活）

struct Node {
    int x, y;
    int value;
};

// 自定义比较类（最小堆）
struct Compare {
    bool operator()(const Node& a, const Node& b) {
        // 返回true表示a的优先级低于b
        // 对于最小堆：value小的优先级高
        return a.value > b.value;  // 注意这里用>，不是<
    }
};

int main() {
    // 最小堆，按value从小到大
    priority_queue<Node, vector<Node>, Compare> pq;
    
    pq.push({1, 2, 10});
    pq.push({3, 4, 5});
    pq.push({5, 6, 15});
    
    cout << pq.top().value << endl;  // 输出5（最小值）
    
    return 0;
}

3. Lambda表达式（C++11+，需要技巧）

// 注意：Lambda不能直接作为模板参数，需要包装
auto cmp = [](int a, int b) { return a > b; };  // 最小堆比较函数

// 方法1：使用decltype和函数指针（不常用）
priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);

// 方法2：使用function（推荐）
#include <functional>
priority_queue<int, vector<int>, function<bool(int, int)>> pq(cmp);

四、竞赛实战：四大经典应用

应用1：维护动态最大值/最小值

// 实时获取数据流中的最大值
class MaxFinder {
private:
    priority_queue<int> maxHeap;
    
public:
    void add(int num) {
        maxHeap.push(num);
    }
    
    int getMax() {
        if (maxHeap.empty()) return INT_MIN;
        return maxHeap.top();
    }
    
    void removeMax() {
        if (!maxHeap.empty()) {
            maxHeap.pop();
        }
    }
};

// 同理，可以封装最小堆

应用2：合并K个有序链表（重要！）

struct ListNode {
    int val;
    ListNode* next;
    
    // 重载<运算符（用于最小堆）
    bool operator<(const ListNode& other) const {
        return val > other.val;  // 注意：最小堆要用>
    }
};

ListNode* mergeKLists(vector<ListNode*>& lists) {
    // 最小堆，按节点值排序
    priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq(
        [](ListNode* a, ListNode* b) { return a->val > b->val; }
    );
    
    // 将所有链表的头节点加入堆中
    for (auto head : lists) {
        if (head) pq.push(head);
    }
    
    ListNode dummy(0);
    ListNode* tail = &dummy;
    
    // 每次取最小的节点
    while (!pq.empty()) {
        ListNode* node = pq.top();
        pq.pop();
        
        tail->next = node;
        tail = tail->next;
        
        // 将该节点的下一个节点加入堆中
        if (node->next) {
            pq.push(node->next);
        }
    }
    
    return dummy.next;
}

应用3：哈夫曼编码（贪心算法）

// 计算哈夫曼编码的最小带权路径长度
int huffmanCost(vector<int>& weights) {
    // 最小堆，每次取最小的两个
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    for (int w : weights) {
        minHeap.push(w);
    }
    
    int totalCost = 0;
    
    // 每次合并最小的两个
    while (minHeap.size() > 1) {
        int a = minHeap.top(); minHeap.pop();
        int b = minHeap.top(); minHeap.pop();
        
        int sum = a + b;
        totalCost += sum;
        minHeap.push(sum);
    }
    
    return totalCost;
}

应用4：求中位数（双堆技巧）

class MedianFinder {
private:
    // 最大堆：存储较小的一半（堆顶是最大值）
    priority_queue<int> left;
    // 最小堆：存储较大的一半（堆顶是最小值）
    priority_queue<int, vector<int>, greater<int>> right;
    
public:
    void addNum(int num) {
        // 优先加入左边
        left.push(num);
        
        // 平衡：左边堆顶可能大于右边堆顶，需要交换
        if (!left.empty() && !right.empty() && left.top() > right.top()) {
            right.push(left.top());
            left.pop();
        }
        
        // 平衡大小：保证left的大小 >= right的大小，且最多大1
        if (left.size() > right.size() + 1) {
            right.push(left.top());
            left.pop();
        } else if (right.size() > left.size()) {
            left.push(right.top());
            right.pop();
        }
    }
    
    double findMedian() {
        if (left.size() > right.size()) {
            return left.top();
        }
        return (left.top() + right.top()) / 2.0;
    }
};

五、与set/multiset的区别

特性	priority_queue	set/multiset
底层实现	二叉堆	红黑树
时间复杂度	插入O(log n)，取最值O(1)	所有操作O(log n)
是否有序	只能访问最值，内部有序但不暴露	全部有序，可以遍历
查找任意元素	不支持	支持
删除任意元素	不支持	支持
空间复杂度	较低（数组存储）	较高（树节点）

选择建议：

• 只需要取最值，不需要查找删除中间元素 → priority_queue
• 需要有序遍历或查找删除任意元素 → set/multiset

六、常见错误与坑点

1. 默认是最小堆还是最大堆？

// 错误：以为是最大堆
priority_queue<int, vector<int>, greater<int>> pq;  // 这是最小堆！

// 记住口诀：
// 默认：priority_queue<int> → 最大堆
// greater<int> → 最小堆
// less<int> → 最大堆（默认）

2. 自定义比较函数的逻辑

struct Node {
    int val;
    // 错误：逻辑写反
    bool operator<(const Node& other) const {
        // 对于最大堆，应该返回val < other.val
        // 返回true表示this优先级低于other
        return val > other.val;  // 错误！这样成了最小堆
    }
};

3. 尝试遍历优先队列

priority_queue<int> pq = {3, 1, 4, 1, 5};

// 错误：没有迭代器，不能这样遍历
for (int x : pq) {  // 编译错误！
    cout << x << " ";
}

// 正确：边pop边输出
while (!pq.empty()) {
    cout << pq.top() << " ";
    pq.pop();  // 注意：遍历后会清空队列！
}

4. 保存原始数据

// 需要同时保存原始数据时
vector<int> data = {3, 1, 4, 1, 5};
priority_queue<int> pq(data.begin(), data.end());

// 现在pq是独立的，修改data不影响pq
// 但pop会改变pq，data不受影响

七、性能优化技巧

1. 预分配空间

// vector作为底层容器可以预分配
vector<int> data;
data.reserve(100000);  // 预分配空间

// 但priority_queue本身没有reserve方法
// 可以先预分配vector，再用它构造priority_queue
vector<int> container;
container.reserve(n);
priority_queue<int, vector<int>> pq(less<int>(), container);

2. 使用emplace替代push（C++11）

struct Node {
    int x, y;
    Node(int a, int b) : x(a), y(b) {}
};

priority_queue<Node> pq;

// push需要构造临时对象
pq.push(Node(1, 2));  // 构造临时对象，然后拷贝

// emplace直接构造（效率更高）
pq.emplace(1, 2);  // 直接构造在堆内存中

3. 延迟删除技巧（Lazy Deletion）

// 场景：需要删除非堆顶元素
// 技巧：标记删除，实际pop时跳过
unordered_map<int, int> invalid;  // 记录无效元素及其次数
priority_queue<int> pq;

void push(int val) {
    pq.push(val);
}

void remove(int val) {
    invalid[val]++;  // 标记为无效
}

int top() {
    // 跳过无效的堆顶元素
    while (!pq.empty()) {
        int val = pq.top();
        if (invalid.count(val) && invalid[val] > 0) {
            invalid[val]--;
            pq.pop();
        } else {
            return val;
        }
    }
    return -1;  // 队列为空
}

八、实战代码模板

#include <bits/stdc++.h>
using namespace std;

class PriorityQueueUtils {
public:
    // 模板1：动态维护最大值
    class DynamicMax {
    private:
        priority_queue<int> maxHeap;
    public:
        void insert(int val) { maxHeap.push(val); }
        int getMax() { return maxHeap.empty() ? INT_MIN : maxHeap.top(); }
        void removeMax() { if (!maxHeap.empty()) maxHeap.pop(); }
        bool empty() { return maxHeap.empty(); }
        int size() { return maxHeap.size(); }
    };
    
    // 模板2：动态维护最小值
    class DynamicMin {
    private:
        priority_queue<int, vector<int>, greater<int>> minHeap;
    public:
        void insert(int val) { minHeap.push(val); }
        int getMin() { return minHeap.empty() ? INT_MAX : minHeap.top(); }
        void removeMin() { if (!minHeap.empty()) minHeap.pop(); }
        bool empty() { return minHeap.empty(); }
        int size() { return minHeap.size(); }
    };
    
    // 模板3：求第K大的元素（使用最小堆）
    static int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> minHeap;
        
        for (int num : nums) {
            minHeap.push(num);
            if (minHeap.size() > k) {
                minHeap.pop();  // 保持堆大小为k
            }
        }
        
        return minHeap.top();  // 堆顶就是第k大的元素
    }
    
    // 模板4：求第K小的元素（使用最大堆）
    static int findKthSmallest(vector<int>& nums, int k) {
        priority_queue<int> maxHeap;
        
        for (int num : nums) {
            maxHeap.push(num);
            if (maxHeap.size() > k) {
                maxHeap.pop();  // 保持堆大小为k
            }
        }
        
        return maxHeap.top();  // 堆顶就是第k小的元素
    }
};

int main() {
    // 示例1：动态最大值
    PriorityQueueUtils::DynamicMax maxQ;
    maxQ.insert(10);
    maxQ.insert(5);
    maxQ.insert(20);
    cout << "当前最大值: " << maxQ.getMax() << endl;  // 20
    
    // 示例2：求第K大的元素
    vector<int> nums = {3, 2, 1, 5, 6, 4};
    int k = 2;
    cout << "第" << k << "大的元素: " 
         << PriorityQueueUtils::findKthLargest(nums, k) << endl;  // 5
    
    return 0;
}

九、总结要点

1. 核心特性：

   • 默认最大堆：priority_queue<int>
   • 最小堆：priority_queue<int, vector<int>, greater<int>>
   • 只能访问堆顶，不能遍历

2. 时间复杂度：

   • 插入：O(log n)
   • 删除堆顶：O(log n)
   • 获取堆顶：O(1)

3. 常用模式：

   • 求第K大/小：维护大小为K的堆
   • 合并K个序列：用堆维护当前最小值
   • 贪心算法：每次取最优元素

4. 竞赛技巧：

   • 双堆维护中位数
   • 延迟删除处理非堆顶删除
   • 预分配底层vector空间

十、记忆技巧

把优先队列想象成一个自动排序的盒子：

• 默认盒子：每次取出的都是最大的
• 最小堆盒子：每次取出的都是最小的
• 只能从顶部拿东西，不能看中间有什么

记住这两个关键点：

1. 需要快速取最值，不需要遍历 → 用priority_queue
2. 自定义比较时：返回true表示优先级低，false表示优先级高

优先队列是算法竞赛中的核心数据结构，尤其是在图论和贪心算法中应用广泛。多练习相关题目，培养用堆思考问题的直觉。